#include<bits/stdc++.h>
#include <unordered_map>
//试着用一下unordered_map的stl库;
/*因为如果自建图的话过程过于繁杂，本题的重点应该在dijkstra和Floyd以及IO交互
  所以使用unordered_map来减轻繁杂枯燥的建图过程
 by 706 lsh;;;
 */
#define reg
using namespace std;

struct view_point{
	string name;
	string describe;
	view_point(){};
	view_point(string name,string describe){
		this->name=name;	this->describe=describe;
	};};//结构体定义，7.6 
struct Map{
	unordered_map<int,view_point> spots;				//存储景点
	unordered_map<int,unordered_map<int,int>> uvlist;	//路径矩阵
	void addSpot(int num,string name,string describe){
		spots[num]=view_point(name,describe);
	}
	void addPath(int u,int v,int weight){
		uvlist[u][v]=weight;
		uvlist[u][v]=weight;
	}
	void deleSpot(int num){
		spots.erase(num);
		uvlist.erase(num);//找到u==num的;
		for(auto& yidui : uvlist){//找到那对中第二个是num的，其实就是找到v==num的
			yidui.second.erase(num);
		}
	}//可能还可以添加一个单纯删掉路径的708lsh;;;
	
	
	vector<vector<int>> floyd(vector<vector<int>>& next) {
		int n = spots.size();
		vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
		//创建nxn充满INT_MAX的矩阵
		for (int i = 0; i < n; ++i) {
			dist[i][i] = 0;
		}//对角肯定0；
		
		for (const auto& u : uvlist) {
			for (const auto& v : u.second) {
				dist[u.first][v.first] = v.second;
				next[u.first][v.first] = v.first;
			}
		}//从unordered图变到matrix 708lsh;;;
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						next[i][j] = next[i][k]; 
					}
				}
			}
		}
		
		return dist;
	}
	vector<int> constructPath(int u, int v, vector<vector<int>>& next) {
		if (next[u][v] == -1) return {}; //使用next数组
		
		vector<int> path = {u};
		while (u != v) {
			u = next[u][v];
			path.push_back(u);
		}
		return path;
	}

	bool findPathDFS(int start, int end, vector<int>& path, unordered_map<int, bool>& visited) {
		path.push_back(start);
		visited[start] = true;
		if (start == end) return true;
		
		for (const auto& neighbor : uvlist[start]) {
			if (!visited[neighbor.first]) {
				if (findPathDFS(neighbor.first, end, path, visited)) {
					return true;
				}
			}
		}
		
		path.pop_back();
		return false;
	}
	void findAllPathsDFS(int start, int end, vector<int>& path, unordered_map<int, bool>& visited, vector<vector<int>>& allPaths) {
		path.push_back(start);
		visited[start] = true;
		if (start == end) {
			allPaths.push_back(path);
		} else {
			for (const auto& neighbor : uvlist[start]) {
				if (!visited[neighbor.first]) {
					findAllPathsDFS(neighbor.first, end, path, visited, allPaths);
				}
			}
		}
		path.pop_back();
		visited[start] = false;
	}
	void queryOnePath(int start, int end) {
		vector<int> path;
		unordered_map<int, bool> visited;
		if (findPathDFS(start, end, path, visited)) {
			cout << "从 " << spots[start].name << " 到 " << spots[end].name << " 的一条通路是: ";
			for (reg int spot : path) {
				cout << spots[spot].name << " ";
			}
			cout << endl;
		} else {
			cout << "从 " << spots[start].name << " 到 " << spots[end].name << " 没有通路" << endl;
		}
	}
	
	// 查询所有路径7.8 lsh;;;
	void queryAllPaths(int start, int end) {
		vector<int> path;
		unordered_map<int, bool> visited;
		vector<vector<int>> allPaths;
		findAllPathsDFS(start, end, path, visited, allPaths);
		if (!allPaths.empty()) {
			cout << "从 " << spots[start].name << " 到 " << spots[end].name << " 的所有路径如下:" << endl;
			for (const auto& p : allPaths) {
				for (reg int spot : p) {
					cout << spots[spot].name << " ";
				}
				cout << endl;
			}
		} else {
			cout << "从 " << spots[start].name << " 到 " << spots[end].name << " 没有路径" << endl;
		}
	}
};


void displayMenu() {
	cout << "校园导游系统菜单：" << endl;
	cout << "1. 添加景点" << endl;
	cout << "2. 添加路径" << endl;
	cout << "3. 删除景点" << endl;
	cout << "4. 查询景点信息" << endl;
	cout << "5. 查询两景点之间的一条路径" << endl;
	cout << "6. 查询两景点之间的所有路径" << endl;
	cout << "7. 查询两景点之间的最短路径" << endl;
	cout << "0. 退出系统" << endl;
}

void handleUserInput(Map& map) {
	int choice;
	do {
		displayMenu();
		cin >> choice;
		switch (choice) {
			case 1: {
				int num;
				string name, describe;
				cout << "请输入“景点编号 名称 描述”：" << endl;
				cin >> num >> name;
				cin.ignore();
				getline(cin, describe);
				map.addSpot(num, name, describe);
				break;
			}
			case 2: {
				int u, v, weight;
				cout << "请输入路径的起点编号、终点编号和路径长度：" << endl;
				cin >> u >> v >> weight;
				map.addPath(u, v, weight);
				break;
			}
			case 3: {
				int num;
				cout << "请输入要删除的景点编号：" << endl;
				cin >> num;
				map.deleSpot(num);
				break;
			}
			case 4: {
				int num;
				cout << "请输入景点编号：" << endl;
				cin >> num;
				if (map.spots.find(num) != map.spots.end()) {
					cout << "景点名称: " << map.spots[num].name << endl;
					cout << "景点描述: " << map.spots[num].describe << endl;
				}
				else {
					cout << "景点不存在" << endl;
				}
				break;
			}
			case 5: {
				int start, end;
				cout << "请输入起点和终点编号：" << endl;
				cin >> start >> end;
				map.queryOnePath(start, end);
				break;
			}
			case 6: {
				int start, end;
				cout << "请输入起点和终点编号：" << endl;
				cin >> start >> end;
				map.queryAllPaths(start, end);
				break;
			}
			case 7: {
				int start, end;
				cout << "请输入起点和终点编号：" << endl;
				cin >> start >> end;
				vector<vector<int>> next(map.spots.size(), vector<int>(map.spots.size(), -1));
				vector<vector<int>> dist = map.floyd(next);
				vector<int> path = map.constructPath(start, end, next);
				if (!path.empty()) {
					cout << "从 " << map.spots[start].name << " 到 " << map.spots[end].name << " 的最短路径是: ";
					for (int spot : path) {
						cout << map.spots[spot].name << " ";
					}
					cout << endl;
					cout << "路径长度: " << dist[start][end] << endl;
				}
				else {
					cout << "从 " << map.spots[start].name << " 到 " << map.spots[end].name << " 没有路径" << endl;
				}
				break;
			}
		case 0:
			cout << "退出系统" << endl;
			break;
		default:
			cout << "无效选择，请重新输入" << endl;
		}
	} while (choice != 0);
}








int main(){
	Map map;
	handleUserInput(map);
	return 0;
}
